package sgg_hsp_data_structures.kmp;

/**
 * 我先解释一下字符串的前缀和后缀。如果字符串A和B，存在A=BS，
 * 其中S是任意的非空字符串，那就称B为A的前缀。例如，”Harry”
 * 的前缀包括{”H”, ”Ha”, ”Har”, ”Harr”}，我们把所有前缀组成的集合，
 * 称为字符串的前缀集合。同样可以定义后缀A=SB， 其中S是任意的非空字符串，
 * 那就称B为A的后缀，例如，”Potter”的后缀包括{”otter”, ”tter”, ”ter”, ”er”, ”r”}，
 * 然后把所有后缀组成的集合，称为字符串的后缀集合。要注意的是，字符串本身并不是自己的后缀。
 * <p>
 * PMT中的值是字符串的前缀集合与后缀集合的交集中最长元素的长度
 * <p>
 * 例如，对于”aba”，它的前缀集合为{”a”, ”ab”}，后缀 集合为{”ba”, ”a”}。两个集合的交集为{”a”}，
 * 那么长度最长的元素就是字符串”a”了，长 度为1，所以对于”aba”而言，它在PMT表中对应的值就是1。
 * 再比如，对于字符串”ababa”，它的前缀集合为{”a”, ”ab”, ”aba”, ”abab”}，
 * 它的后缀集合为{”baba”, ”aba”, ”ba”, ”a”}， 两个集合的交集为{”a”, ”aba”}，
 * 其中最长的元素为”aba”，长度为3。
 * <p>
 * 作者：海纳
 * 链接：https://www.zhihu.com/question/21923021/answer/281346746
 * 来源：知乎
 * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 * <p>
 * 解释清楚这个表是什么之后，我们再来看如何使用这个表来加速字符串的查找，以及这样用的道理是什么。如图 1.12 所示，
 * 要在主字符串"ababababca"中查找模式字符串"abababca"。如果在 j 处字符不匹配，那么由于前边所说的模式字符串
 * PMT 的性质，主字符串中 i 指针之前的 PMT[j −1] 位就一定与模式字符串的第 0 位至第 PMT[j−1] 位是相同的。
 * 这是因为主字符串在 i 位失配，也就意味着主字符串从 i−j 到 i 这一段是与模式字符串的 0 到 j 这一段是完全相同的。
 * 而我们上面也解释了，模式字符串从 0 到 j−1 ，在这个例子中就是”ababab”，其前缀集合与后缀集合的交集的最长元素为”abab”，
 * 长度为4。所以就可以断言，主字符串中i指针之前的 4 位一定与模式字符串的第0位至第 4 位是相同的，即长度为 4 的后缀与前缀相同。
 * 这样一来，我们就可以将这些字符段的比较省略掉。具体的做法是，保持i指针不动，然后将j指针指向模式字符串的PMT[j −1]位即可。简言之，
 * 以图中的例子来说，在 i 处失配，那么主字符串和模式字符串的前边6位就是相同的。又因为模式字符串的前6位，它的前4位前缀和后4位后缀是相同的，
 * 所以我们推知主字符串i之前的4位和模式字符串开头的4位是相同的。就是图中的灰色部分。那这部分就不用再比较了。
 */
public class KMPTest {
    private static int getIndexOf(String s, String m) {
        if (s == null || m == null || m.length() < 1 || s.length() < m.length()) {
            return -1;
        }
        char[] str1 = s.toCharArray();
        char[] str2 = m.toCharArray();
        //---------log-------
        printArr(str2);
        //---------log-------

        int i1 = 0;
        int i2 = 0;
        int[] next = getNextArray(str2);
        while (i1 < str1.length && i2 < str2.length) {
            if (str1[i1] == str2[i2]) {
                i1++;
                i2++;
            } else if (next[i2] == -1) {
                i1++;
            } else {
                i2 = next[i2];
            }
        }


        "".trim();
        return i2 == str2.length ? i1 - i2 : -1;
    }

    private static int[] getNextArray(char[] ms) {
        if (ms.length == 1) {
            return new int[]{-1};
        }
        int[] next = new int[ms.length];
        next[0] = -1;
        next[1] = 0;
        int i = 2;
        int cn = 0;
        while (i < next.length) {
            System.out.println();
            System.out.println("i : " + i + " | " + "next.length : " + next.length);
            System.out.println("ms[i - 1] : " + ms[i - 1] + " | " + "ms[cn] : " + ms[cn] + " | " + "cn : " + +cn);

            if (ms[i - 1] == ms[cn]) {
                next[i++] = ++cn;
            } else if (cn > 0) {
                cn = next[cn];
            } else {
                next[i++] = 0;
            }
            printArr(next);
        }
        return next;
    }

    public static void main(String[] args) {
        String str = "abcabcababaccc";
//        String match = "ababa";
        String match = "ababa";
        System.out.println(getIndexOf(str, match));
//        System.out.println(kmp(str, match));
        calculateMaxMatchLengths(match);

    }

    private static void printArr(char[] arr) {
        System.out.print("next[] : ");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " , ");
        }
        System.out.println();
    }

    private static void printArr(int[] arr) {
        System.out.print("next[] : ");
        for (int item : arr) {
            System.out.print(item + " , ");
        }
        System.out.println();
    }


    ///&&&&&&&&&&&&&&&&&&&&&


    // 构造模式串 pattern 的最大匹配数表
    static int[] calculateMaxMatchLengths(String pattern) {
        int[] maxMatchLengths = new int[pattern.length()];
        int maxLength = 0;
        for (int i = 1; i < pattern.length(); i++) {
            while (maxLength > 0 && pattern.charAt(maxLength) != pattern.charAt(i)) {
                maxLength = maxMatchLengths[maxLength - 1]; // ①
            }
            if (pattern.charAt(maxLength) == pattern.charAt(i)) {
                maxLength++; // ②
            }
            maxMatchLengths[i] = maxLength;
        }
        printArr(maxMatchLengths);
        return maxMatchLengths;
    }
    ///&&&&&&&&&&&&&&&&&&&&&

    ////////////////////////
    private static int kmp(String str1, String str2) {
        int i = 0;
        int j = 0;

        char[] t = str1.toCharArray();
        char[] p = str2.toCharArray();

        char[] next = new char[p.length];

        while (i < t.length && j < p.length) {
            if (j == -1 || t[i] == p[j]) {
                i++;
                j++;
            } else {
                j = next[j];
            }
        }

        if (j == p.length)
            return i - j;
        else
            return -1;
    }

//    private static void getNext(char *p, int *next) {
//        next[0] = -1;
//        int i = 0, j = -1;
//
//        while (i < strlen(p)) {
//            if (j == -1 || p[i] == p[j]) {
//                ++i;
//                ++j;
//                next[i] = j;
//            } else
//                j = next[j];
//        }
//    }

//    void cal_next(char *str, int *next, int len) {
//        next[0] = -1;//next[0]初始化为-1，-1表示不存在相同的最大前缀和最大后缀
//        int k = -1;//k初始化为-1
//        for (int q = 1; q <= len-1; q++) {
//            while (k > -1 && str[k + 1] != str[q]) {//如果下一个不同，那么k就变成next[k]
//                k = next[k];//往前回溯
//            }
//            if (str[k + 1] == str[q]){//如果相同，k++
//                k = k + 1;
//            }
//            next[q] = k;//这个是把算的k的值（就是相同的最大前缀和最大后缀长）赋给next[q]
//        }
//    }


    /**
     * 代码随想录
     * <p>
     * 初始化
     * 前后缀不相同
     * 前后缀相同
     * next
     * <p>
     * aabaaf
     * 010120
     */
    public static int[] getNextBiliBili(String s) {
        char[] schar = s.toCharArray();
        int[] next = new int[schar.length];
        // i 后缀末尾 -- j 前缀末尾
        int j = 0;
        next[0] = 0;
        for (int i = 1; i < schar.length; i++) {
            while (j > 0 && schar[i] != schar[j]) {
                j = next[j - 1];
            }
            j++;
            next[i] = j;


        }


        return next;
    }

}
